## return a formatted hex string from a numeric address
def hex_str(addr)
    sprintf("0x%8x",addr)
end

## Function object class
## This class contains the name, address, and local stack usage of a
## function.  It also keeps the list of callees to the function.
class Fncall
    # Name of the function
    attr_reader :name

    # Local stack usage
    attr_reader :stklocal
    attr_reader :stktotal

    attr_writer :stklocal , :callee_biggest
    attr_writer :indirect_callees
    attr_reader :indirect_callees

    @@max_stack_val = 1000000  # Class variable
    

    def initialize(name, addr=0)
        # Name of the function
        @name = name          
        # address of the function
        @fnaddr = addr
        # Local stack occupancy
        @stklocal = 0

        # Max stack occupancy of this function and its callees
        # It is nil until it has been computed
        @stktotal = nil

        # Array of callee addresses.
        @callees = Array.new

        # Is this function part of a recursion
        @recursion = false

        # The callee with the largest stack occupancy
        @callee_biggest = nil

        # Does this function have indirect callees
        @indirect_callees = false

        # Use a marker to detect recursion
        # when becoming part of a function call chain, mark this
        @in_cycle = false
    end



    # Is the function recursive
    def recursive?
        return @recursion
    end



    # Get the name of the function as a string
    def to_s
        @name
    end


    # Get the address of the function as an integer
    def to_i
        @fnaddr
    end


    # print the address of the function
    def hex_addr
        s = sprintf("0x%08x",@fnaddr)
        return s
    end


    # Does this function have any callees, direct or indirect
    def any_callees?
        if (self.empty  && (@indirect_callees == false))
            return false
        else
            return true
        end
    end




    #add a new callee if not already existing 
    def add_callee(callee_addr)
        if (!@callees.member?(callee_addr))
            @callees.push(callee_addr)
        end
    end




    # Add indirect callee addresses (input as Array) to this
    # function
    def indirect_callee(callee_addrs)
        if (! @indirect_callees)
            puts "@name does not have indirect callees"
            return
        end

        if ( callee_addrs.empty?)
            puts "Invalid callee addresses for #{@name}"
            return
        end

        # error check done,  now we add the callees
        @callees.concat(callee_addrs)

        # remove duplications if any
        @callees.uniq!

        # mark this function as no longer having indirect callees
        @indirect_callees = false

    end




    # are there any callees?
    def empty
        @callees.empty?
    end




    #enumerate the callees
    def each
        @callees.each  { |c| yield(c)}
    end



    # follow a function through its biggest callees
    def follow(program)
        # Return this function
        yield(self)
        
        # Follow to the biggest callee and yield that
        if (@callee_biggest)
            tf = program[@callee_biggest]

            # Call follow on the biggest callee (recursion)
            tf.follow(program) { |f|
                yield(f)
            }
        end
    end




    # Find the maximum stack of this function, check for recursion,
    # and find the biggest callee.
    # the program object which contains a list of functions is 
    # given as a parameter
    # Return the total stack usage of this function and its children
    def traverse(program)
        if (@in_cycle)
            puts "RECURSION alert #{@name}"
            @stktotal = @@max_stack_val
            @recursion = true
            return @stktotal
        end

        # If stktotal is not nil then the stack computation has 
        # already been performed and does not need to be repeated
        if (@stktotal)
            return @stktotal
        end
        

        # Create an array of the child stack sizes (to find the biggest)
        child_stks = Array.new

        # If there are indirect callees then stack is indeterminate
        if (@indirect_callees)
            @stktotal = @@max_stack_val
            return @stktotal
        end




        @in_cycle = true    # For recursion detection
        
        # For all the callees, find the max
        if (!@callees.empty?)
            @callees.each{|subfunc_addr|

                subfunc = program.findbyaddr(subfunc_addr)
                if (!subfunc)
                    subfunc_addr_hex = hex_str(subfunc_addr)
                    puts "#{@name}: callee with addr #{subfunc_addr} (#{subfunc_addr_hex}) not found"
                    child_stks.push(@@max_stack_val)
                    break
                end
                
                # Recursively call traverse on all the children.
                # Drill down
                subfunc_stk = subfunc.traverse(program)
                child_stks.push(subfunc_stk)
            }
        end
        @in_cycle = false
        


        if (@recursion)
            @stktotal = @@max_stack_val
            @callee_biggest = nil
        else

            if (child_stks.empty?)  # No children
                max_stk_val = 0
            else
                max_stk_val = child_stks.max

                # Which callee was the biggest
                # What is the index of the biggest stack value
                max_stk_ind = child_stks.index(max_stk_val)
                
                if(max_stk_ind)
                    @callee_biggest = @callees[max_stk_ind]
                end
            end

            #puts "Child stacks for #{@name} are "
            #child_stks.each{ |s| puts " #{s} "}
            @stktotal = @stklocal + max_stk_val
        end


        return @stktotal
    end

    

end







# The Program class is contains a list of function objects.
# It is implemented as a hash
#  Keys = Address,  Value = Object reference for the function
class Program < Hash

    @@max_stack_val = 1000000  # Class variable

    # Override the default iterator to provide the value instead of
    # the key
    def each
        each_value { |val|
            yield(val)
        }
    end


    # Find a function in the Program by name
    def findbyname(fname)
        detect {|f| 
            f.to_s == fname
        }
    end
    

    # Find a function by address
    # This is simply looking up a function in the Hash table using its
    # address as a key
    def findbyaddr(addr)
        return self[addr]
    end



    # Fix all the indirect function calls
    # fcalllist is a hash with the function name as the key
    # and the Array of callees as the value 
    def fixindcalls(fcalllist)
        
        # For each hash value (fn, callees), fix the fn's indirect call
        # info 
        fcalllist.each {|f, fcall|
            fn = findbyname(f)
            if (!fn) 
                puts "#{f} not found in program"
                break
            end

            callee_addrs = Array.new

            # For each callee for this function, find its address and
            # Create an array of these callee addresses
            fcall.each{ |callee_name|
                callee = findbyname(callee_name)
                if (!callee) 
                    puts "#{callee_name} not found in program"
                    break
                end
                callee_addrs.push(callee.to_i)
            }


            # Add the calles to the funtion.
            fn.indirect_callee(callee_addrs)
        }
    end  # fixindcalls



end  #Class Program







# Class to hold the usage description for each architecture
class DescribeUsage
    def DescribeUsage.mspgcc
        str = "MSPGCC USAGE: the input for this architecture " +
            "is the  *.lst file created from the appropriate" +
            ".elf file by msp430-objdump -dSt x.elf"

    end
end









# Class to hold all methods to analyze disassembly from different architectures.
class Disassembler
    

    def Disassembler.mspgcc(disassembly, program = Program.new)
        # Disassembly takes the form such as 
        #000040dc <task_assert>:
        #    40dc:       0b 12           push    r11             ;
        #    40de:       0a 12           push    r10             ;
        #    40e0:       09 12           push    r9              ;
        #    40e2:       08 12           push    r8              ;
        #    40e4:       0a 4e           mov     r14,    r10     ;
        #    40e6:       09 4d           mov     r13,    r9      ;
        #
        #0000413e <drawline>:
        #    413e:	0b 12       	push	r11		;
        #    4140:	31 80 50 00 	sub	#80,	r1	;#0x0050
        #
        #0000411e <kb_cmd_write>:
        #411e:	21 83       	decd	r1		;

        # 00004150 <f9>:
        #void f9(uint8_t x, indirect_fn_t findirect)
        # {
        # 4150:	0b 12       	push	r11		
        # 4152:	0a 12       	push	r10		
        # 4154:	31 50 f6 ff 	add	#-10,	r1	;#0xfff6
        # 4158:	0b 4e       	mov	r14,	r11	

        # We should only count push and stack modifications, immediately after
        # function definition.
        # Sometimes ther are push commands to pass arguments to funcs
        # They are also popped.

        # Function calls look like this.
        #    40c2:	b0 12 0a 66 	call	#26122		;#0x660a

        #    4058:	b0 12 4e 60 	call	#0x604e	

        #  Calls to a function pointer
        #    79d4:	87 12       	call	r7		;
        


        # -------------- Regular Expression -----------
        f_RE = /^([[:xdigit:]]{2,16})\s+<(.*)>:.*$/
        #f_RE = /<(.*)>:.*$/

        
        stk1_RE = /^\s*[[:xdigit:]]{2,16}:.*\bpush.*$/
        #    4140:	31 80 50 00 	sub	#80,	r1	;#0x0050
        stk2_RE = /^\s*[[:xdigit:]]{2,16}:.*\bsub\s*#(.*),\s*r1\s.*$/

        # 41a0:	31 82       	sub	#8,	r1	;r2 As==11

        stk3_RE = /^\s*[[:xdigit:]]{2,16}:.*\bdecd\s.*$/

        # 4154:	31 50 f6 ff 	add	#-10,	r1	;#0xfff6
        stk4_RE = /^\s*[[:xdigit:]]{2,16}:.*\badd\s*#(.*),\s*r1\s.*$/

        #stk4_RE = /^\s*[[:xdigit:]]{2,16}:.*r1\s.*$/
        #disassem_RE = /^\s*[[:xdigit:]]{2,16}:.*;.*$/
        disassem_RE = /^\s*[[:xdigit:]]{2,16}:.*$/
        #call_dir_RE = /^\s*[[:xdigit:]]{2,16}:.*\bcall.*;#(.*)$/
        call_dir_RE = /^\s*[[:xdigit:]]{2,16}:.*\bcall.*#(.*)$/
        call_ind_RE = /^\s*[[:xdigit:]]{2,16}:.*\bcall.*$/


        curr_fn = nil
        addstkval = false;
        disassembly.each_line{ |line|
            if (line =~ f_RE)
                # Example:: 
                #000040dc <task_assert>:
                curr_fn = Fncall.new($2, $1.hex)
                program[$1.hex] = curr_fn;
                addstkval = true;  # Valid stack instructions may follow
                #puts "FUNC (#{$2} @#{$1})" + line.chomp


            elsif (line =~ stk1_RE)
                # Example:: 
                #    40de:       0a 12           push    r10             ;            
                curr_fn.stklocal = curr_fn.stklocal + 2;
                #puts "PUSH " + line.chomp

            elsif (line =~ stk2_RE)
                # Example::
                #    4140:	31 80 50 00 	sub	#80,	r1	;#0x0050
                stk_incr = $1.to_i
                if (stk_incr > 0)
                    curr_fn.stklocal = curr_fn.stklocal + $1.to_i;
                end


            elsif (line =~ stk3_RE)
                # Example:: 
                #411e:	21 83       	decd	r1		;
                curr_fn.stklocal = curr_fn.stklocal + 2;

                #puts "PUSH " + line.chomp


            elsif (line =~ stk4_RE)
                # Example::
                # 4154:	31 50 f6 ff 	add	#-10,	r1	;#0xfff6
                stk_incr = $1.to_i
                if (stk_incr < 0)
                    curr_fn.stklocal = curr_fn.stklocal - $1.to_i;
                end

                #puts "STK  " + line.chomp



            elsif (line =~ disassem_RE)
                # If the line is valid disassembler but is not any of the
                # above matches then stop stack size parsing for this
                # function
                # However, our detection of end of stack processing is
                # not accurate so we don't use it.
                addstkval = false;

                # Direct function call
                if (line =~ call_dir_RE)

                    if !(curr_fn.any_callees?)
                        # This is the first function to be added
                        # Add two bytes for call overhead
                        curr_fn.stklocal = curr_fn.stklocal + 2;
                    end

                    curr_fn.add_callee($1.hex)
                    #puts "CALLD (#{$1.hex}) " + line.chomp
                elsif (line =~ call_ind_RE)
                    if !(curr_fn.any_callees?)
                        # This is the first function to be added
                        # Add two bytes for call overhead
                        curr_fn.stklocal = curr_fn.stklocal + 2;
                    end

                    curr_fn.indirect_callees =  true
                    #puts "CALLI " + line.chomp
                end



            end

        }

        return program
    end




end

